Nicole Immorlica
Abstract:
We consider the problem of converting an arbitrary approximation
algorithm for a single-parameter optimization problem into a
computationally efficient truthful mechanism. We ask for reductions
that are black-box, meaning that they require only oracle access to
the given algorithm and in particular do not require explicit
knowledge of the problem constraints. Such a reduction is known to be
possible, for example, for the social welfare objective when the goal
is to achieve Bayesian truthfulness and preserve social welfare in
expectation. We show that a black-box reduction for the social welfare
objective is not possible if the resulting mechanism is required to be
truthful in expectation and to preserve the worst-case approximation
ratio of the algorithm to within a subpolynomial factor. Further, we
prove that for other objectives such as makespan, no black-box
reduction is possible even if we only require Bayesian truthfulness
and an average-case performance guarantee.
Joint work with Shuchi Chawla and Brendan Lucier.